package com.leetcode.algorithm.y22.m07;

/**
 * 1894. 找到需要补充粉笔的学生编号
 * 
 * https://leetcode.cn/problems/find-the-student-that-will-replace-the-chalk/
 * 
 * @author jie.deng
 *
 */
class Question1894Solution01 {
	
	public int chalkReplacer(int[] chalk, int k) {
		int len = chalk.length;
		int[] prefixSumArr = new int[len];
		prefixSumArr[0] = chalk[0];
		if (prefixSumArr[0] > k) {
			return 0;
		}
		for (int i = 1; i < len; i++) {
			prefixSumArr[i] = prefixSumArr[i - 1] + chalk[i];
			if (prefixSumArr[i] > k) {
				return i;
			}
		}
		k %= prefixSumArr[len - 1];
		return searchGreaterIdx(prefixSumArr, k);
	}

	private int searchGreaterIdx(int[] prefixSumArr, int k) {
		int len = prefixSumArr.length;
		int left = 0;
		int right = len - 1;
		// (left,right]
		while (left < right) {
			int mid = left + ((right - left) >> 1);
			if (prefixSumArr[mid] <= k) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return right;
	}
    
}